package com.cuz.series.linklist;

/***
 * https://leetcode.cn/problems/add-two-numbers/
 */
public class 链表6两数相加 {

    public static void main(String[] args) {
        ListNode node1 = ListNode.of1(2, 4, 3);
        ListNode node2 = ListNode.of1(5, 6, 7);
        ListNode sum = addTwoNumer2(node1, node2);
        sum.print();
    }

    public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }
        //是否存在进位
        boolean carry = false;
        //哑节点
        ListNode preHead = new ListNode();
        //遍历中使用tail 连接每一个新节点 ，tail是新链表的尾巴
        ListNode tail = preHead;

        //都不为null的时候
        while (l1 != null && l2 != null) {
            int sum = l1.val + l2.val;
            //之前存在进位 那么需要加1
            if (carry) {
                sum += 1;
                carry = false;
            }
            //现在和大于0 那么对10 取模，标记需要进位加1
            if (sum >= 10) {
                sum = sum % 10;
                carry = true;
            }
            //新节点
            tail.next = new ListNode(sum);

            //前进
            tail = tail.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        //都为null
        if (l1 == null && l2 == null) {
            //但是存在进位
            // 比如 1，2，4 和 2，3，7=>3->5=>1 => (1) 这里就是这个1
            if (carry) {
                tail.next = new ListNode(1);
            }
            //返回
            return preHead.next;
        }
        //剩下一个更长的
        ListNode lessNode = l1 == null ? l2 : l1;
        tail.next = lessNode;
        //如果没有进位 那么直接连接返回
        if (!carry) {
            return preHead.next;
        }
        // 存在进位 那么需要进行调整
        while (true) {
            //进位那么+1
            lessNode.val++;

            //大于10 取模
            if (lessNode.val >= 10) {
                lessNode.val = lessNode.val % 10;
                //如果到达尾部 加一个1 上去
                //比如 1，2，3 和 1，1，7，9
                //最后的 9加1 等于10，需要加一个节点1
                if (lessNode.next == null) {
                    lessNode.next = new ListNode(1);
                    break;
                }
            } else {
                //如果没有进位 那么直接返回
                break;
            }
            lessNode = lessNode.next;
        }

        return preHead.next;
    }


    public static ListNode addTwoNumer2(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }

        ListNode preHead = new ListNode();
        ListNode tail = preHead;
        boolean carry = false;
        while (l1 != null || l2 != null) {
            int sum = nodeValNullReturn0(l1) + nodeValNullReturn0(l2);
            if (carry) {
                sum = sum + 1;
                carry = false;
            }
            if (sum >= 10) {
                sum = sum % 10;
                carry = true;
            }
            tail.next = new ListNode(sum);
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
            tail = tail.next;
        }
        if (carry) {
            tail.next = new ListNode(1);
        }
        return preHead.next;
    }


    private static int nodeValNullReturn0(ListNode node) {
        if (node == null) {
            return 0;
        }
        return node.val;
    }
}
